判断t1树中是否有与t2树完全相同的子树

[编程题]判断t1树中是否有与t2树完全相同的子树

热度指数：18890 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定彼此独立的两棵二叉树，树上的节点值两两不同，判断 t1 树是否有与 t2 树完全相同的子树。

子树指一棵树的某个节点的全部后继节点

数据范围：树的节点数满足 $0 < n \le 500000$ ，树上每个节点的值一定在32位整型范围内

进阶：空间复杂度: $O(1)$ ，时间复杂度 $O(n)$

示例1

输入

{1,2,3,4,5,6,7,#,8,9},{2,4,5,#,8,9}

输出

true

备注:

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Python 3

梦幻泡影oO

class Solution:
    def isContains(self , root1: TreeNode, root2: TreeNode) -> bool:

        def dfs_same(t1, t2):
            if not t1 and not t2: return True
            if not t1 or not t2: return False
            l, r = dfs_same(t1.left, t2.left), dfs_same(t1.right, t2.right)
            return l and r and t1.val == t2.val

        def dfs(x):
            if not x: return not root2
            return dfs_same(x, root2) or dfs(x.left) or dfs(x.right)

        return dfs(root1)

发表于 2022-03-14 16:08:58 回复(0)

Python 3

Joy_9

class Solution:
    def isContains(self , t1: TreeNode, t2: TreeNode) -> bool:
        # write code here
        if not t1 and t2:
            return False
        if not t2 and t1:
            return False
        if not t2 and not t1:
            return True
        if t1.val==t2.val:
            return self.isContains(t1.left, t2.left) and self.isContains(t1.right, t2.right)
        else:
            return self.isContains(t1.left, t2)&nbs***bsp;self.isContains(t1.right, t2)

发表于 2022-01-11 06:48:18 回复(0)

Python 3

JSFaner

class Solution:
    def isContains(self , root1: TreeNode, root2: TreeNode) -> bool:
        def recur(root):
            if not root: return "#"
            return '*'+str(root.val)+recur(root.left)+recur(root.right)
        return recur(root2) in recur(root1)

发表于 2021-11-21 20:16:13 回复(0)

Python 3

牛客38477449号

class Solution:
    def isContains(self , root1 , root2 ):
        # write code here
        if not root1:
            return False
        if not root2:
            return True
        self.res = False
        def dfs(root1, root2):
            if not root1:
                return
            if root1.val == root2.val:
                if self.process(root1, root2):
                    self.res = True
                    return 
            dfs(root1.left, root2)
            dfs(root1.right, root2)
        dfs(root1, root2)
        return self.res
    
    
    def process(self, root1, root2):
        if root1 == None and root2 == None:
            return True
        if root1 == None and root2 != None:
            return False
        if root1 != None and root2 == None:
            return False
        if root1.val == root2.val:
            return self.process(root1.left, root2.left) and self.process(root1.right, root2.right)
        else:
            return False

发表于 2021-09-06 20:21:12 回复(0)